package basic.courseLearn07;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//并查集--简易实现
public class MyUnionFindSet {

    public HashMap<Node, ArrayList<Node>> setMap=new HashMap<>();

    //初始情况，每个节点都是一个并查集
    public void init(List<Node> nodes){
        for (Node node : nodes) {
            ArrayList<Node> list = new ArrayList<>();
            list.add(node);
            setMap.put(node, list);
        }
    }

    //合并两个并查集
    public void union(Node node1, Node node2){
        if (isSameSet(node1, node2)){
            return;
        }
        //1. 获取两个并查集
        ArrayList<Node> set1 = setMap.get(node1);
        ArrayList<Node> set2 = setMap.get(node2);
        //2. 合并两个并查集
        ArrayList<Node> totalSet = new ArrayList<Node>();
        totalSet.addAll(set1);
        totalSet.addAll(set2);
        //3. 更新并查集
        for (Node node : set1) {
            setMap.put(node, totalSet);
        }
        for (Node node : set2) {
            setMap.put(node, totalSet);
        }
    }

    //判断两个节点是否属于同一个并查集
    public boolean isSameSet(Node node1, Node node2){
        //1. 获取两个并查集
        ArrayList<Node> set1 = setMap.get(node1);
        ArrayList<Node> set2 = setMap.get(node2);
        //2. 判断两个并查集是否相同,即判断地址是否相同
        return set1 == set2;
    }

    @Test
    public void test(){
        List<Node> nodes=new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            nodes.add(new Node(i));
        }
        init(nodes);
        union(nodes.get(0), nodes.get(1));
        union(nodes.get(2), nodes.get(3));
        union(nodes.get(4), nodes.get(5));
        union(nodes.get(6), nodes.get(7));
        union(nodes.get(8), nodes.get(9));
        System.out.println(isSameSet(nodes.get(0), nodes.get(1))); //true
        System.out.println(isSameSet(nodes.get(2), nodes.get(3))); //true
        System.out.println(isSameSet(nodes.get(4), nodes.get(5))); //true
        System.out.println(isSameSet(nodes.get(6), nodes.get(7))); //true
        System.out.println(isSameSet(nodes.get(8), nodes.get(9))); //true
        System.out.println(isSameSet(nodes.get(0), nodes.get(2))); //false
        System.out.println(isSameSet(nodes.get(1), nodes.get(3))); //false
        System.out.println(isSameSet(nodes.get(4), nodes.get(6))); //false
        System.out.println(isSameSet(nodes.get(5), nodes.get(7))); //false
        System.out.println(isSameSet(nodes.get(8), nodes.get(0))); //false
    }



}
